package StackAndQueue;

import java.util.*;

public class MaxSlidingWindow239 {
    public static void main(String[] args) {
        for (int i : maxSlidingWindow1(new int[]{1,3,-1,-3,5,3,6,7}, 3)) {
            System.out.print(i + " ");
        }
    }

    public static int[] maxSlidingWindow1(int[] nums, int k) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }


    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 1) {
            return nums;
        }
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int[] ints = new int[nums.length - k + 1];

        int i = 0;
        int j = 0;
        int max = Integer.MIN_VALUE;
        while (i < nums.length - k + 1) {
            while (j < i + k) {
//                deque.add(nums[j]);
                j++;
            }
            for (int l = i; l < j - 1; l++) {
                if (nums[l] - nums[l + 1] > 0) {
                    max = max > nums[l] ? max : nums[l];
                }else{
                    max = max > nums[l+1] ? max : nums[l+1];
                }
            }
            ints[i] = max;
            deque.poll();
            i++;
            max= Integer.MIN_VALUE;
        }
        return ints;
    }

    public static int max1(Deque<Integer> deque) {
        return 0;
    }

    public static int max(Deque<Integer> deque) {

        int[] ints = new int[deque.size()];
        int i = 0;
        int len = deque.size();
        while (i < len) {
            ints[i] = deque.pop();
            deque.add(ints[i]);
            i++;
        }
        Arrays.sort(ints);
        return ints[len - 1];
    }
}
